/*
 * Lab6B.cpp
 *
 *  Created on: 2011-04-22
 *      Author: A Varghese
 */

#include <iostream>

class Node{
public:
	Node(int d): data(d){left=right=NULL;}
	int data;	Node* left;  Node* right;
};

class Tree{
public:
	Tree(): root(NULL){}
	~Tree(){ delete_postorder(root);}
	void add(int d){
		if (root==NULL)
			root = new Node(d);
		else
			add_inorder(root, d);
	}
	friend std::ostream& operator <<( std::ostream& o, Tree& t){
		o << "Inorder traversal:   ";
		t.print_inorder(o, t.root);

		o << std::endl << "Preorder traversal:  ";
		t.print_preorder(o, t.root);

		o << std::endl << "Postorder traversal: ";
		t.print_postorder(o, t.root);
		o << std::endl;
		return o;
	}
private:
	Node* root;

	void add_inorder(Node* t, int d){
		if (d <= t->data)
			if (t->left == NULL)
				t->left = new Node(d);
			else add_inorder(t->left, d);
		else
			if (t->right == NULL)
				t->right = new Node(d);
			else add_inorder(t->right, d);
	}

	void print_inorder(std::ostream& o, Node*t){
		if (t==NULL) return;
		print_inorder(o, t->left);
		o << t->data << " ";
		print_inorder(o, t->right);
	}
	void print_preorder(std::ostream& o, Node*t){
		if (t==NULL) return;
		print_preorder(o, t->left);
		o << t->data << " ";
		print_preorder(o, t->right);
	}
	void print_postorder(std::ostream& o, Node*t){
		if (t==NULL) return;
		print_postorder(o, t->left);
		o << t->data << " ";
		print_postorder(o, t->right);
	}

	void delete_postorder(Node* t){
		if (t== NULL) return;
		delete_postorder( t->left );  t->left = NULL;
		delete_postorder( t->right ); t->right = NULL;
		delete t;
	}
};



int main(){
	Tree t;
	int data[] = { -2, 3, 10, -21, 35, 3, 85, -2, 100};

	for (int i=0; i<9; i++)
		t.add( data[i] );

	std::cout << t << std::endl;

	std::cout << "Done!";
}

